package me.qingy.programmatic;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * 类似快慢指针
 *
 * @author qingy
 * @since 2021-08-19
 */
public class RemoveDuplicates {

    /**
     * 原地删除重复元素，空缺向前位移，空间复杂度必须为 O(1)
     *
     * @return 删除后数组的新长度
     */
    public int removeDuplicates(int[] nums) {
        int k = 0; // [0,k] 元素
        for (int i = 1; i < nums.length; i++) {
            if (nums[k] != nums[i]) {
                nums[++k] = nums[i]; // k 移至 i 位将不重复元素放入
            }
        }
        return k + 1;
    }

    @Test
    public void testRemoveDuplicates() {
        Assertions.assertEquals(2, removeDuplicates(new int[]{1, 1, 2}));
        Assertions.assertEquals(5, removeDuplicates(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}));
    }

}
